package 二叉树高频题目_下_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/
public class Code04_BalancedBinaryTree {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public static boolean balance;
    public boolean isBalanced(TreeNode root) {
        // balance是全局变量，所有调用过程共享
        // 所以每次判断开始时，设置为true
        balance = true;
        height(root);
        return balance;
    }

    // 一旦发现不平衡，返回什么高度已经不重要了
    public static int height(TreeNode cur){
        if(cur == null || !balance){
            return 0;
        }
        int lh = height(cur.left);
        int rh = height(cur.right);
        // 发现不平衡，则balance=false
        if(Math.abs(lh - rh) > 1){
            balance = false;
        }
        return Math.max(lh, rh) +1;
    }
}
